{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Array in Sets of K Consecutive Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPossibleDivide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #划分数组为连续数字的集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个正整数&nbsp;<code>k</code>，请你判断是否可以把这个数组划分成一些由&nbsp;<code>k</code>&nbsp;个连续数字组成的集合。<br />\n",
    "如果可以，请返回 <code>true</code>；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,3,4,4,5,6], k = 4\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>数组可以分成 [1,2,3,4] 和 [3,4,5,6]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3,2,2,1,1], k = 3\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], k = 3\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>数组不能分成几个大小为 3 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>此题目与 846 重复：<a href=\"https://leetcode-cn.com/problems/hand-of-straights/\" target=\"_blank\">https://leetcode-cn.com/problems/hand-of-straights/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-array-in-sets-of-k-consecutive-numbers](https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-array-in-sets-of-k-consecutive-numbers](https://leetcode.cn/problems/divide-array-in-sets-of-k-consecutive-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,3,4,4,5,6]\\n4', '[3,2,1,2,3,4,3,4,5,9,10,11]\\n3', '[1,2,3,4]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import Dict, List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        count: Dict[int, int] = Counter(nums)\n",
    "        uniqs: List[int] = sorted(count.keys())\n",
    "            \n",
    "        start: int = 0\n",
    "        expect: int = uniqs[0]\n",
    "        \n",
    "        while True:\n",
    "            while start < len(uniqs) and count[uniqs[start]] == 0:\n",
    "                start += 1\n",
    "            if start == len(uniqs):\n",
    "                break\n",
    "\n",
    "            expect = uniqs[start]\n",
    "            n: int = 0\n",
    "            while n < k and (start + n) < len(uniqs):\n",
    "                if uniqs[start + n] != expect or count[expect] == 0:\n",
    "                    return False\n",
    "                count[expect] -= 1\n",
    "                n += 1\n",
    "                expect += 1\n",
    "                \n",
    "            if n < k:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        c = Counter(nums)\n",
    "        s = sorted(c)\n",
    "        for start in s:\n",
    "            target = c[start]\n",
    "            if target > 0:\n",
    "                for i in range(start, start+k):\n",
    "                    if c[i] < target:\n",
    "                        return False\n",
    "                    c[i] -= target\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n%k!=0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for val in nums:\n",
    "            if cnt[val]==0:\n",
    "                continue\n",
    "            for v in range(val,val+k):\n",
    "                if cnt[v]==0:\n",
    "                    return False\n",
    "                cnt[v] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k != 0:  # 如果nums的长度不是k的倍数，肯定不满足题意\n",
    "            return False\n",
    "        group_nums = len(nums) // k  # 最终将分成几组\n",
    "        group_count = 0\n",
    "        counter = collections.Counter(nums)\n",
    "        nums.sort()  # 一定要排序后再处理\n",
    "\n",
    "        for num in nums:  # 遍历每一个数字\n",
    "            if counter[num] == 0:  # 如果该数字对应的次数为0，说明当前数字已经被用完，就跳到下一个数字进行判断\n",
    "                continue\n",
    "            for i in range(k):  #\n",
    "                if counter[num + i] == 0:  # 如果从当前的num开始的到后num+k-1中某个数字已经没有可用的了，则为False\n",
    "                    return False\n",
    "                counter[num + i] -= 1  # 否则的话对数字出现次数减 1\n",
    "            group_count += 1  # 如果完美完成一次for循环，说名找到了一组满足条件的组合\n",
    "\n",
    "            if group_count == group_nums:  # 如果组数等于目标组数，就满足题意返回True\n",
    "                return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        if n % k:\r\n",
    "            return(False)\r\n",
    "        dic = {}\r\n",
    "        for v in nums:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "        nums.sort()\r\n",
    "        for v in nums:\r\n",
    "            if dic[v] != 0:\r\n",
    "                for i in range(k):\r\n",
    "                    if v + i not in dic or dic[v + i] == 0:\r\n",
    "                        return(False)\r\n",
    "                    else:\r\n",
    "                        dic[v + i] -= 1\r\n",
    "        return(True)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        for start in sorted(cnt):\n",
    "            if cnt[start]:\n",
    "                cs = cnt[start]\n",
    "                for d in range(k):\n",
    "                    if cnt[start + d] < cs:\n",
    "                        return False\n",
    "                    cnt[start + d] -= cs\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        nums.sort()\n",
    "        num_dict = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            num_dict[num] += 1\n",
    "        for num in nums:\n",
    "            if num_dict[num] == 0:\n",
    "                continue\n",
    "            for num2 in range(num, num + k):\n",
    "                if num_dict[num2] == 0:\n",
    "                    return False\n",
    "                num_dict[num2] -= 1\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: list[int], k: int) -> bool:\n",
    "        nums.sort()\n",
    "        count = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            count[num] += 1\n",
    "        keys = count.keys()\n",
    "        for key in keys:\n",
    "            value = count[key]\n",
    "            if not value:\n",
    "                continue\n",
    "            for i in range(k):\n",
    "                count[key + i] -= value\n",
    "                if count[key + i] < 0:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        nums.sort()\n",
    "        if len(nums)%k:\n",
    "            return False\n",
    "        #n = len(nums)//k\n",
    "        count = Counter(nums)\n",
    "        idx = 0\n",
    "        #print(nums,count)\n",
    "        for num in nums:\n",
    "            if count[num] == 0:\n",
    "                continue\n",
    "            for x in range(num,num+k):\n",
    "                if count[x] == 0:\n",
    "                    return False\n",
    "                count[x] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k: return False\n",
    "        cnt = Counter(nums)\n",
    "        sn = sorted(cnt)\n",
    "        for x in range(sn[0], sn[-1]+k):\n",
    "            if cnt[x] < 0:return False\n",
    "            if cnt[x]:\n",
    "                t = cnt[x]\n",
    "                for i in range(1, k):\n",
    "                    cnt[x+i] -= t\n",
    "        return True\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        if n % k:\r\n",
    "            return(False)\r\n",
    "        dic = {}\r\n",
    "        for v in nums:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "        nums.sort()\r\n",
    "        for v in nums:\r\n",
    "            if dic[v] != 0:\r\n",
    "                for i in range(k):\r\n",
    "                    if v + i not in dic or dic[v + i] == 0:\r\n",
    "                        return(False)\r\n",
    "                    else:\r\n",
    "                        dic[v + i] -= 1\r\n",
    "        return(True)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        # 哈希表+排序\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        \n",
    "        count = defaultdict(int)\n",
    "        for num in nums:\n",
    "            count[num] += 1\n",
    "        \n",
    "        for key in sorted(count.keys()):\n",
    "            value = count[key]\n",
    "            if value == 0:\n",
    "                continue\n",
    "            for i in range(k):\n",
    "                count[key+i] -= value\n",
    "                if count[key+i] < 0:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        c = Counter(nums)\n",
    "        s = sorted(c)\n",
    "        for start in s:\n",
    "            target = c[start]\n",
    "            if target > 0:\n",
    "                for i in range(start, start+k):\n",
    "                    if c[i] < target:\n",
    "                        return False\n",
    "                    c[i] -= target\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k : return False\n",
    "        c = Counter(nums)\n",
    "        nums.sort()\n",
    "        for x in nums:\n",
    "            if c[x] == 0:\n",
    "                continue\n",
    "            for i in range(x, x + k):\n",
    "                if c[i] == 0:\n",
    "                    return False\n",
    "                c[i] -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k:\n",
    "            return False\n",
    "        cnt = Counter(nums)\n",
    "        for i in sorted(nums):\n",
    "            if cnt[i] <= 0:\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                if i + j not in cnt or cnt[i + j] <= 0:\n",
    "                    return False\n",
    "                cnt[i + j] -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        nums.sort()\n",
    "        if len(nums)%k:\n",
    "            return False\n",
    "        #n = len(nums)//k\n",
    "        count = Counter(nums)\n",
    "        idx = 0\n",
    "        #print(nums,count)\n",
    "        for num in nums:\n",
    "            if count[num] == 0:\n",
    "                continue\n",
    "            for x in range(num,num+k):\n",
    "                if count[x] == 0:\n",
    "                    return False\n",
    "                count[x] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        cnt=collections.Counter(nums)\n",
    "\n",
    "        n=len(nums)\n",
    "        if n%k!=0:\n",
    "            return False\n",
    "        t=n//k\n",
    "\n",
    "        for i in range(t):\n",
    "            mi=min(cnt.keys())\n",
    "            for j in range(mi,mi+k):\n",
    "                if cnt[j]==0:\n",
    "                    return False\n",
    "                cnt[j]-=1\n",
    "                if cnt[j]==0:\n",
    "                    del(cnt[j])\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k:\n",
    "            return False\n",
    "        \n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for num in nums:\n",
    "            if cnt[num] == 0:\n",
    "                continue\n",
    "\n",
    "            for num in range(num, num + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k:\n",
    "            return False\n",
    "        di = dict()\n",
    "        for num in nums:\n",
    "            di[num] = di.get(num, 0) + 1\n",
    "        keys = sorted(di.keys())\n",
    "        for key in keys:\n",
    "            if di[key]:\n",
    "                for j in range(key + 1, key + k):\n",
    "                    if j not in di or di[j] < di[key]:\n",
    "                        return False\n",
    "                    di[j] -= di[key]\n",
    "                di[key] = 0\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        counter = Counter(nums)\n",
    "        for num in nums:\n",
    "            if counter[num] == 0:\n",
    "                continue\n",
    "            for it in range(num, num+k):\n",
    "                if counter[it] == 0:\n",
    "                    return False\n",
    "                counter[it] -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums)%k!=0:\n",
    "            return False\n",
    "        counter=collections.Counter(nums)\n",
    "        group_num=len(nums)//k\n",
    "        group_time=0\n",
    "        nums.sort()\n",
    "\n",
    "        for num in nums:\n",
    "            if counter[num]==0:\n",
    "                continue\n",
    "            for i in range(k):\n",
    "                if counter[num+i]==0:\n",
    "                    return False\n",
    "                counter[num+i]-=1\n",
    "            group_time+=1\n",
    "            \n",
    "            if group_time==group_num:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k :\n",
    "            return False\n",
    "        a = {}\n",
    "        for num in nums:\n",
    "            if num in a:\n",
    "                a[num] += 1\n",
    "            else:\n",
    "                a[num] = 1\n",
    "        l = list(a.keys())\n",
    "        l.sort()\n",
    "        for i in l:\n",
    "            m = a[i]\n",
    "            if m > 0:\n",
    "                for j in range(k):\n",
    "                    nu = i + j\n",
    "                    if nu not in a:\n",
    "                        return False\n",
    "                    elif a[nu] < m:\n",
    "                        return False\n",
    "                    else:\n",
    "                        a[nu] -= m\n",
    "        return True\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        nums.sort()\n",
    "        d = dict()\n",
    "        for n in nums:\n",
    "            if n not in d:\n",
    "                d[n] = 1\n",
    "            else:\n",
    "                d[n] += 1\n",
    "\n",
    "        for n in d:\n",
    "            if d[n] > 0:\n",
    "                for i in range(1, k):\n",
    "                    if (n + i) not in d or d[n + i] < d[n]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        d[n + i] -= d[n] \n",
    "                d[n] = 0\n",
    "        \n",
    "        lv = list(d.values())\n",
    "        return not any(lv)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        if k == 1:\n",
    "            return True\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d[num] += 1\n",
    "            else:\n",
    "                d[num] = 1\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            if d[nums[i]] > 0:\n",
    "                d[nums[i]] -= 1\n",
    "                for j in range(1,k):\n",
    "                    if (nums[i]+j) not in d or d[nums[i]+j] == 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        d[nums[i]+j] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k != 0: return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for n in range(x, x + k):\n",
    "                if cnt[n] == 0:\n",
    "                    return False\n",
    "                cnt[n] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        # 特殊情况：如果数组长度不是k的倍数，则不能分割\n",
    "        if len(nums) % k != 0:\n",
    "            return False\n",
    "        \n",
    "        # 计算每个数字的出现次数\n",
    "        count = Counter(nums)\n",
    "        \n",
    "        # 对数字进行排序\n",
    "        for num in sorted(count):\n",
    "            # 如果当前数字的计数值为非零，我们需要找到k个连续数字并减少它们的计数值\n",
    "            while count[num] > 0:\n",
    "                for i in range(k):\n",
    "                    if count[num + i] <= 0:\n",
    "                        return False\n",
    "                    count[num + i] -= 1\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        num_freq = collections.Counter(nums)\n",
    "        a = sorted(num_freq.keys())\n",
    "        for x in a:\n",
    "            f = num_freq[x]\n",
    "            if f > 0:\n",
    "                for y in range(x + 1, x + k):\n",
    "                    if num_freq[y] >= f:\n",
    "                        num_freq[y] -= f\n",
    "                    else:\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        hand_map = collections.defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            hand_map[nums[i]] += 1\n",
    "        for key in sorted(hand_map.keys()):\n",
    "            value = hand_map[key]\n",
    "            if value == 0:\n",
    "                continue\n",
    "            for i in range(k):\n",
    "                hand_map[key+i] -= value\n",
    "                if hand_map[key+i] < 0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        count = Counter(nums)\n",
    "        for num in nums:\n",
    "            if count[num] == 0:\n",
    "                continue\n",
    "            for i in range(num, num+k):\n",
    "                if count[i] == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    count[i] -= 1\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        cnt = Counter(nums)\n",
    "        for x in sorted(nums):\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        \n",
    "        num_map = defaultdict(int)\n",
    "        for num in nums:\n",
    "            num_map[num] += 1\n",
    "        \n",
    "        num_list = []\n",
    "        nums = list(num_map.keys())\n",
    "        nums.sort()\n",
    "        # print(num_map, nums)\n",
    "        for num in nums:\n",
    "            if num_map[num] == 0:\n",
    "                continue\n",
    "            \n",
    "            count = num_map[num]\n",
    "            for num_i in range(num + 1, num + k):\n",
    "                if num_map[num_i] < count:\n",
    "                    return False\n",
    "                num_map[num_i] -= count\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = Counter(nums) \n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False \n",
    "        while cnt: \n",
    "            mn = min(cnt) \n",
    "            x = cnt[mn]\n",
    "            base = mn\n",
    "            for i in range(k):\n",
    "                if cnt[base+i] < x:\n",
    "                    return False \n",
    "                cnt[base+i] -= x\n",
    "                if cnt[base+i] == 0:\n",
    "                    del cnt[base+i] \n",
    "        return True \n",
    "         \n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        count = Counter(nums)\n",
    "        num_dict = defaultdict(int)\n",
    "\n",
    "        for num in sorted(count.keys()):\n",
    "            if count[num] > 0:\n",
    "                m = count[num]\n",
    "                for i in range(k):\n",
    "                    next_num = num + i\n",
    "                    if count[next_num] < m:\n",
    "                        return False\n",
    "                    count[next_num] -= m\n",
    "                    if count[next_num] == 0:\n",
    "                        del count[next_num]\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if k==1:\n",
    "            return True\n",
    "\n",
    "        dic = dict()\n",
    "        for n in nums:\n",
    "            if n in dic:\n",
    "                dic[n] += 1\n",
    "            else:\n",
    "                dic[n] = 1\n",
    "        \n",
    "        t = list(dic.keys())\n",
    "\n",
    "        t.sort()        \n",
    "\n",
    "        for i in range(len(t)):\n",
    "            if dic[t[i]] == 0:\n",
    "                continue\n",
    "            count = dic[t[i]]\n",
    "            for j in range(k):\n",
    "                if t[i]+j not in dic or dic[t[i]+j] < count:\n",
    "                    return False\n",
    "                dic[t[i]+j] -= count\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "\n",
    "        nums.sort()\n",
    "        counter = collections.Counter(nums)\n",
    "        for num in nums:\n",
    "            if counter[num] == 0:\n",
    "                continue\n",
    "\n",
    "            for j in range(num, num + k):\n",
    "                if counter[j] <= 0:\n",
    "                    return False\n",
    "                counter[j] -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "#         n = len(nums)\n",
    "#         if n % k != 0:\n",
    "#             return False\n",
    "\n",
    "#         maxN = 10 ** 5 + 1\n",
    "#         maxN = max(nums) + 1\n",
    "#         counter = [0] * maxN\n",
    "#         for num in nums:\n",
    "#             counter[num] += 1\n",
    "\n",
    "#         # print(counter)\n",
    "\n",
    "#         for i in range(maxN):\n",
    "#             # if counter[i] == 0:\n",
    "#             #     continue\n",
    "#             while counter[i] > 0:\n",
    "#                 for j in range(k):\n",
    "#                     if i + j >= maxN or counter[i + j] <= 0:\n",
    "#                         return False\n",
    "#                     counter[i + j] -= 1\n",
    "#                 # print(counter)\n",
    "#         return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = collections.Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums)%k!=0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        d={}\n",
    "        for i in nums:\n",
    "            if i not in d:\n",
    "                d[i]=1\n",
    "            else:\n",
    "                d[i]+=1\n",
    "        for i in range(len(nums)//k):\n",
    "            res=[]        \n",
    "            for v in d.keys():\n",
    "                if len(res)==k:\n",
    "                    break\n",
    "                if d[v] !=0:\n",
    "                    d[v]-=1\n",
    "                    res.append(v)\n",
    "                else:\n",
    "                    continue\n",
    "            if len(res)!=k:\n",
    "                return False\n",
    "            # if len(res)==1 and k!=1:\n",
    "            #     return False\n",
    "            if sorted(list(set(res)))!=res or len(res)!=len(set(res)):\n",
    "                    return False\n",
    "            for i in range(1,len(res)):\n",
    "                if res[i-1]!=res[i]-1:\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k:\n",
    "            return False\n",
    "        cnt = Counter(nums)\n",
    "        for i in sorted(nums):\n",
    "            if cnt[i] <= 0:\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                if i + j not in cnt or cnt[i + j] <= 0:\n",
    "                    return False\n",
    "                cnt[i + j] -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        a = {}\n",
    "        for num in nums:\n",
    "            if num in a:\n",
    "                a[num] += 1\n",
    "            else:\n",
    "                a[num] = 1\n",
    "        l = list(a.keys())\n",
    "        l.sort()\n",
    "        for i in l:\n",
    "            m = a[i]\n",
    "            if m > 0:\n",
    "                for j in range(k):\n",
    "                    nu = i + j\n",
    "                    if nu not in a:\n",
    "                        return False\n",
    "                    elif a[nu] < m:\n",
    "                        return False\n",
    "                    else:\n",
    "                        a[nu] -= m\n",
    "        return True\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        hand_map = collections.defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            hand_map[nums[i]] += 1\n",
    "        for key in sorted(hand_map.keys()):\n",
    "            value = hand_map[key]\n",
    "            if value == 0:\n",
    "                continue\n",
    "            # count = 0\n",
    "            for i in range(k):\n",
    "                hand_map[key + i] -= value\n",
    "                if hand_map[key + i] < 0:\n",
    "                    return False\n",
    "                # count += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        count=collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            count[num]+=1\n",
    "        \n",
    "        for key in sorted(count.keys()):\n",
    "            value=count[key]\n",
    "            if value==0:\n",
    "                continue\n",
    "            for i in range(k):\n",
    "                count[key+i]-=value\n",
    "                if count[key+i]<0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        \"\"\"\n",
    "        这个函数首先检查数组长度是否可以被 k 整除，如果不能，直接返回 False。然后，\n",
    "        使用 Counter 统 计每个数字的出现次数。接着，对计数字典按数字升序进行遍历，对于每个数字，\n",
    "        尽量将其分配给一个集合，如果无法完成分配，则返回 False。如果成功分配完所有数字，返回 True。\n",
    "        \n",
    "        首先统计频数，\n",
    "        再按key排序，遍历，不断更新字典中的 频数\n",
    "        \"\"\"\n",
    "        if len(nums) % k != 0:\n",
    "            return False\n",
    "        \n",
    "        counter = Counter(nums)\n",
    "        for num in sorted(counter.keys()):\n",
    "            if counter[num] > 0: #只有counter中还有频数，才会进入循环\n",
    "                for i in range(k-1, -1,-1):\n",
    "                    next_num = num + i\n",
    "                    if counter[next_num] < counter[num]:\n",
    "                        return False\n",
    "                    counter[next_num] -= counter[num] #把 首位数据的频数剪掉\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        \n",
    "        num_map = defaultdict(int)\n",
    "        for num in nums:\n",
    "            num_map[num] += 1\n",
    "        \n",
    "        num_list = []\n",
    "        nums = list(num_map.keys())\n",
    "        nums.sort()\n",
    "        # print(num_map, nums)\n",
    "        while nums:\n",
    "            num = nums.pop()\n",
    "            if num_map[num] == 0:\n",
    "                continue\n",
    "            \n",
    "            for i in range(1, k):\n",
    "                if i > len(nums):\n",
    "                    return False\n",
    "                if nums[-i] != num - i:\n",
    "                    return False\n",
    "                num_map[nums[-i]] -= num_map[num]\n",
    "                if num_map[nums[-i]] < 0:\n",
    "                    return False\n",
    "\n",
    "            # print(num, num_map)\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        from sortedcontainers import SortedDict\n",
    "        mydict = SortedDict()\n",
    "        for x in nums:\n",
    "            if x not in mydict.keys():\n",
    "                mydict[x] = 1\n",
    "            else:\n",
    "                mydict[x] += 1\n",
    "        for key in mydict.keys():\n",
    "            if mydict[key] > 0:\n",
    "                count = mydict[key]\n",
    "                for i in range(key + 1, key + k):\n",
    "                    if mydict.get(i, -1) < count:\n",
    "                        return False\n",
    "                    mydict[i] -= count\n",
    "                    if mydict[i] == 0:\n",
    "                        del mydict[i]\n",
    "        return True\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % k != 0:\n",
    "            return False\n",
    "        from sortedcontainers import SortedDict\n",
    "        mydict = SortedDict()\n",
    "        for x in nums:\n",
    "            if x not in mydict.keys():\n",
    "                mydict[x] = 1\n",
    "            else:\n",
    "                mydict[x] += 1\n",
    "        for key in mydict.keys():\n",
    "            count = mydict[key]\n",
    "            for i in range(key + 1, key + k):\n",
    "                if mydict.get(i, -1) < count:\n",
    "                    return False\n",
    "                mydict[i] -= count\n",
    "                if mydict[i] == 0:\n",
    "                    del mydict[i]\n",
    "        return True\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        if len(nums) % k > 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cnt = Counter(nums)\n",
    "        for x in nums:\n",
    "            if cnt[x] == 0:\n",
    "                continue\n",
    "            for num in range(x, x + k):\n",
    "                if cnt[num] == 0:\n",
    "                    return False\n",
    "                cnt[num] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossibleDivide(self, nums: List[int], k: int) -> bool:\n",
    "        ans = True\n",
    "        if k == 1:\n",
    "            return True\n",
    "        lens = len(nums)\n",
    "        if lens % k != 0:\n",
    "            return False\n",
    "        cnt = Counter(nums)\n",
    "        nums.append(inf)\n",
    "        nums = sorted(list(set(nums)),reverse = True)\n",
    "        \n",
    "        now = nums.pop()\n",
    "        while now != inf:\n",
    "            if cnt[now] == 0:\n",
    "                now = nums.pop()\n",
    "                continue\n",
    "            for i in range(now,now+k):\n",
    "                if cnt[i] == 0:\n",
    "                    return False\n",
    "                cnt[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isPossibleDivide(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        from collections import Counter, deque\n",
    "        dic = Counter(nums)\n",
    "        nums = deque(sorted(list(set(nums))))\n",
    " \n",
    "        res = []\n",
    "        while nums:\n",
    "            num = nums[0]\n",
    "            for i in range(k):\n",
    "                target = num + i \n",
    "                if target not in dic:\n",
    "                    return False\n",
    "                dic[target] -= 1\n",
    "                if dic[target] == 0:\n",
    "                    nums.popleft()\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
